package com.tang.algorithm.array;

import java.util.Arrays;

/**
 * @author tlm
 * @version 1.0
 * @date 2020/5/15 20:15
 * 多数元素
 * <p>
 * https://leetcode-cn.com/problems/majority-element/
 */
public class LeetCode169 {
    public static void main(String[] args) {
        int[] a = {2, 2, 1, 1, 1, 2, 2};
        System.out.println(majorityElement(a));
    }

    //解法1 排序
    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    //解法2 摩尔投票法
    public static int majorityElement2(int[] nums) {
        int count = 0;
        Integer res = null;
        for (int num : nums) {
            if (count == 0) {
                res = num;
            }
            count += (num == res) ? 1 : -1;
        }
        return res;
    }
}
